package com.laotang.第_16_章_字典树.力扣_212_单词搜索二;

import java.util.ArrayList;
import java.util.List;

public class _212_word_search_ii {
    private List<String> res = new ArrayList<>();

    private char[][] board;

    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int m;
    private int n;
    private boolean[][] visited;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        this.m = board.length;
        this.n = board[0].length;
        this.visited = new boolean[m][n];

        TrieNode root = buildTrie(words);
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                dfs(row, col, root);
            }
        }

        return res;
    }

    private void dfs(int row, int col, TrieNode node) {
        if (node.children[board[row][col] - 'a'] == null)  return;

        node = node.children[board[row][col] - 'a'];
        if (node.word != null) {
            res.add(node.word);
            node.word = null;
        }

        visited[row][col] = true;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n
                    && !visited[nextRow][nextCol]) {
                dfs(nextRow, nextCol, node);
            }
        }
        visited[row][col] = false;
    }


    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String s : words) {
            TrieNode curr = root;
            for (char c : s.toCharArray()) {
                int index = c - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new TrieNode();
                }
                curr = curr.children[index];
            }
            curr.word = s;
        }
        return root;
    }

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }
}
